package com.leetcode.No0730;

/**
 * @program: Solution
 * @description: 730. 统计不同回文子序列
 * 使用三维数组方案
 * https://leetcode.cn/problems/count-different-palindromic-subsequences/solution/tong-ji-bu-tong-hui-wen-zi-xu-lie-by-lee-7slg/
 * @author: Wang Zhihua
 * @date: 2022-06-10
 */
public class Solution {

    public int countPalindromicSubsequences(String s) {

        int len = s.length();
        int[][][] dp = new int[4][len + 2][len + 2];
        char[] charArray = s.toCharArray();

        for (int i = 0; i < len; ++i) {
            dp[charArray[i] - 'a'][i][i] = 1;
        }

        for (int l = 2; l <= len; ++l) { // 滑动窗口长度
            for (int left = 0; left + l <= len; ++left) { // 滑动窗口左端点
                int right = left + l - 1;

                for  (char c = 'a'; c <= 'd'; ++c) {
                    int intC = c - 'a';

                    if (charArray[left] == c && charArray[left] == charArray[right]) {
                        dp[intC][left][right] = 2;
                        dp[intC][left][right] += dp[0][left + 1][right - 1];
                        dp[intC][left][right] %= 1000000007;
                        dp[intC][left][right] += dp[1][left + 1][right - 1];
                        dp[intC][left][right] %= 1000000007;
                        dp[intC][left][right] += dp[2][left + 1][right - 1];
                        dp[intC][left][right] %= 1000000007;
                        dp[intC][left][right] += dp[3][left + 1][right - 1];
                        dp[intC][left][right] %= 1000000007;

                    } else if (charArray[left] == c && charArray[right] != c) {
                        dp[intC][left][right] = dp[intC][left][right - 1];

                    } else if (charArray[left] != c && charArray[right] == c) {
                        dp[intC][left][right] = dp[intC][left + 1][right];

                    } else {
                        dp[intC][left][right] = dp[intC][left + 1][right - 1];
                    }
                }
            }
        }

        int result = 0;
        result += dp[0][0][len - 1];
        result %= 1000000007;
        result += dp[1][0][len - 1];
        result %= 1000000007;
        result += dp[2][0][len - 1];
        result %= 1000000007;
        result += dp[3][0][len - 1];
        result %= 1000000007;

        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        String s = "bccb";
        System.out.println(solution.countPalindromicSubsequences(s));

        s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba";
        System.out.println(solution.countPalindromicSubsequences(s));
    }

}
